const loop = function () {};

//生成唯一标识
function guid() {
  function S4() {
    return (((1 + Math.random()) * 0x10000) | 0).toString(16).substring(1);
  }
  return (
    S4() +
    S4() +
    "-" +
    S4() +
    "-" +
    S4() +
    "-" +
    S4() +
    "-" +
    S4() +
    S4() +
    S4()
  );
}

//数组转树结构
function arrayToTree(arr, op = {}) {
  const option = Object.assign(
    {
      ch: "children",
      id: "id",
      pid: "pid"
    },
    op
  );
  const map = arr.reduce((prev, curr, idx, arr) => {
    prev[curr[option.id]] = curr;
    return prev;
  }, {});
  const result = [];
  arr.map(item => {
    if (item[option.pid] in map) {
      let parent = map[item[option.pid]];
      parent[option.ch] = parent[option.ch] || [];
      parent[option.ch].push(item);
    } else {
      result.push(item);
    }
  });
  return result;
}

//树结构转数组
function treeToArray(tree, op = {}) {
  const option = Object.assign(
    {
      ch: "children"
    },
    op
  );
  const result = [...tree];
  for (let i = 0; i < result.length; i++) {
    if (!result[i][option.ch]) continue;
    result.splice(i + 1, 0, ...result[i][option.ch]);
  }
  result.map(item => delete item[option.ch]);
  return result;
}

//遍历树结构
function treeForeach(tree, cb, op = {}) {
  const option = Object.assign(
    {
      ch: "children"
    },
    op
  );
  let queue = [...tree],
    node = null;
  while ((node = queue.shift())) {
    cb(node);
    node[option.ch] && queue.unshift(...node[option.ch]);
  }
}

//遍历树结构(回调return false结束遍历)
function foreachTree(tree, cb, op = {}) {
  let option = {
    children: "children"
  };
  option = Object.assign(option, op);
  function initChildren(item, idx, arr) {
    if (cb(item, idx, arr) === false) {
      return false;
    }
    if (
      item[option.children] instanceof Array &&
      item[option.children].length === 0
    ) {
      delete item[option.children];
    }
    if (!item[option.children]) {
      return true;
    }

    for (let i = 0; i < item[option.children].length; i++) {
      if (
        initChildren(item[option.children][i], i, item[option.children]) ===
        false
      ) {
        return false;
      }
    }
  }

  for (let i = 0; i < tree.length; i++) {
    if (initChildren(tree[i], i, tree) === false) {
      break;
    }
  }
  return tree;
}

//格式化树
function formatTree(tree, cb, op = {}) {
  let option = {
    id: "_id",
    children: "children",
    parent: "_parent",
    level: "_level",
    pid: "_pid"
  };
  option = Object.assign(option, op);
  let level = 0;
  function initChildren(item) {
    item[option.level] = ++level;
    item[option.id] = guid();
    cb(item);
    if (
      item[option.children] instanceof Array &&
      item[option.children].length === 0
    ) {
      delete item[option.children];
    }
    if (!item[option.children]) {
      return;
    }
    for (let i = 0; i < item[option.children].length; i++) {
      item[option.children][i][option.pid] = item[option.id];
      item[option.children][i][option.parent] = item;
      initChildren(item[option.children][i]);
      --level;
    }
  }

  for (let i = 0; i < tree.length; i++) {
    level = 0;
    initChildren(tree[i]);
  }
  return tree;
}

//查找节点
function treeFind(tree, cb, op = {}) {
  const option = Object.assign(
    {
      ch: "children"
    },
    op
  );
  for (const item of tree) {
    if (cb(item)) return item;
    if (item[option.ch]) {
      return treeFind(item[option.ch], cb, op);
    }
  }
  return null;
}

//查找节点路径
function treeFindPath(tree, cb, op = {}) {
  const option = Object.assign(
    {
      ch: "children"
    },
    op
  );
  let path = [];
  for (const item of tree) {
    path.push(item);
    if (cb(item)) return path;
    if (item[option.ch]) {
      let chPath = treeFindPath(item[option.ch], cb, op);
      path.push(...chPath);
      if (chPath.length) return path;
    }
    path.pop();
  }
  return path;
}

//过滤树
function filterTree(tree, cb, op = {}) {
  const option = Object.assign(
    {
      ch: "children"
    },
    op
  );
  const result = tree.filter(cb);
  for (let i = 0; i < result.length; i++) {
    if (result[i][option.ch]) {
      result[i][option.ch] = filterTree(result[i][option.ch], cb, op);
    }
  }
  return result;
}

//映射树
function mapTree(tree, cb, op = {}) {
  const option = Object.assign(
    {
      ch: "children"
    },
    op
  );
  const result = tree.map(item => {
    const obj = {
      ...(cb(item) ?? {})
    };
    if (item[option.ch]) obj[option.ch] = item[option.ch];
    return obj;
  });
  for (let i = 0; i < result.length; i++) {
    if (result[i][option.ch]) {
      result[i][option.ch] = mapTree(result[i][option.ch], cb, op);
    }
  }
  return result;
}

export {
  arrayToTree,
  treeToArray,
  treeForeach,
  treeFind,
  treeFindPath,
  foreachTree,
  formatTree,
  filterTree,
  mapTree
};
